In multicast/broadcast applications, data are transmitted from a server to multiple receivers over wired and/or wireless networks. Herein, a “/” is used to indicate alternative names for the same or similar components. A multicast system as used herein is a system in which a server transmits the same data to multiple receivers simultaneously, where the receivers form a subset of all the receivers up to and including all of the receivers. A broadcast system is a system in which a server transmits the same data to all of the receivers simultaneously. That is, a multicast system by definition can include a broadcast system.
The popularity of voice and video applications over mobile computing devices has raised concerns regarding the performance of medium access control (MAC) protocols, which are responsible for allocating shared medium resources to multiple communicating stations and resolving collisions that occur when two or more stations access the medium simultaneously. In the current IEEE 802.11 wireless LANs, the distributed coordination function (DCF) of the MAC protocol layer uses a binary exponential back-off (BEB) algorithm for fundamental channel access. The BEB algorithm mitigates the issue of network collisions by randomizing the timing of medium access among stations that share the communication medium. The timing of channel access in the BEB algorithm is randomized by setting the slot counter to a random integer selected from contention window [0, CW] in each back-off cycle, and CW doubles upon failed data transmissions in last back-off cycle. Here a back-off cycle is a procedure where the back-off slot counter decrements down from an initial maximal value to zero. The simplicity and good performance of BEB contribute to the popularity of IEEE 802.11 DCF/EDCA.
However, as demonstrated by both practical experience and theoretical analysis, the BEB algorithm has some deficiencies. First, the collision probability for a transmission attempt increases exponentially with the number of active stations in the network, which significantly impairs the network throughput for large-scale and/or densely deployed networks. Second, the medium access delay cannot be bounded and the jitter is variable, which may not be suitable for multimedia applications. Third, the opportunity for medium access is not fair among stations. That is, a given station may gain access to the communication medium and get served for a long time. This results in other stations having to greatly defer their access to the medium. Moreover, it turns out that the use of doubling the contention window upon failed transmissions appears to give more transmission opportunities to these successful stations.
Some concepts/terms that may benefit the understanding of the present invention are provided. A frame is a unit of data. That is, data can be packaged in packets or frames or any other convenient format. As used herein a frame is used to indicate data packaged in a format for transmission. A back-off round/stage/cycle is a procedure in which the back-off slot counter counts down from an initial value (maximum) to zero. When the counter reaches zero, a new transmission is attempted. One frame transmission may involve multiple back-off rounds/stages (because of unsuccessful transmission attempts). As used herein a time slot represents a continuous time period during which the back-off slot counter is frozen. It may refer to either a fixed time period (usually several microseconds) sufficient for the physical layer to perform the carrier sensing once, or a varying time period (usually between hundreds of microseconds to several milliseconds, depending on the length of the packet and physical data rate) when a frame is being transmitted over the shared medium. In a network with shared medium, each station freezes or decreases its back-off slot counter based on the resulting status of the physical or virtual carrier sensing of the medium. Hence, because of the shared nature of the medium, the slot count changes are aligned among the stations. The time slot can be used as a basic time unit to make the entire procedure discrete. Positive integers n=1, 2, 3, . . . , N are used to indicate the 1st, 2nd, 3rd, . . . , Nth time slot, and In is used to indicate the status of the shared medium at the nth slot, for example, In=1 when busy and In=0 otherwise. The back-off slot count of station i at the nth time slot is denoted as sloti(n).
In Application Serial Number PCT/US09/001,855, a relaxed deterministic back-off (R-DEB) method was described to overcome issues such as backward compatibility and dependability that are inherent in the deterministic back-off (DEB) method. The R-DEB method selects the back-off slot count in as deterministic a way as possible to reduce or avoid network collisions. The R-DEB method also introduces randomness to this procedure to preserve the flexibility and easy deployment feature of the conventional random back-off methods such as the BEB (binary exponential back-off) method. Hence, the R-DEB method made a compromise between the network efficiency and flexibility, and can be viewed as a combination of the DEB algorithm and BEB algorithm. The initial motivation of the R-DEB algorithm was to adapt the deterministic back-off for video transport systems while maintaining backward compatibility with the previous standards.
The R-DEB operates as follows. A back-off round starts when a station resets its back-off slot count slot(n) to the fixed number M (note that here n is a variable on the timeline). Once it is determined by the physical carrier sensing procedure that the sharing medium is idle for a time slot, the station decreases its back-off slot count by one. If this new slot count satisfies the transmission triggering condition (that is, the new slot count equals one of the elements of the triggering set QT, e.g., slot(n)=k). The node/station/client device/mobile device/mobile terminal will get an opportunity to initiate a data transmission (hence “triggering a transmission”). If no frame is to be sent at this time, the node forgoes the opportunity and continues decreasing its slot count. The result of the data transmission determines whether or not the element k should further remain in the triggering set: if there was a successful transmission then this triggering element remain in the triggering set; if there an unsuccessful data transmission then, with a probability p, a triggering element substitution procedure will be initiated that replaces the old element k with a new one k′ from the interval [0, M]. The R-DEB method included a method and apparatus for selecting an element from the interval [0, M−1] for inclusion in the triggering set QT to reduce network collisions. It should be noted that a station can be a computer, laptop, personal digital assistant (PDA), dual mode smart phone or any other device that can be mobile.
However, further investigation of the R-DEB method has shown that the size of triggering set |QT| has significant effect on system performance. It is easy for one to realize that |QT| should be set to a small value (have a small number of triggering elements) when congestion occurs in the network, and |QT| should be enlarged when sporadic traffic is observed in the network.
EP Application EP 09305479.9 filed 26 May 2009 addressed this problem. First, when a system achieves optimal performance was discussed, then a control method and apparatus to improve the system performance by adaptively adjusting the size of trigger set upon the observed sparseness was described. The throughput of the R-DEB method was analyzed and it was shown that the size of triggering set could be adjusted to achieve optimal system throughput. Based on this analysis, a control method and apparatus to have the size of triggering set controlled around the optimal point, which gave maximized network throughput for the system was described. This control method adjusted the size of triggering set adaptively to the observed network sparseness. In addition, how to adjust the size of triggering set based on some other factors, such as the amount of data in the transmission buffer and network fairness was also discussed. The invention showed that the triggering set could be adaptively maintained with the evolution of network dynamics to achieve better system performance as well as describing a method and apparatus for adaptively adjusting the triggering set with the evolvement of network dynamics to achieve better system performance.
A novel method that seeks to improve the IEEE 802.11 system is described herein. The method of the present invention is directed towards optimal performance even in densely populated/deployed areas. In this approach, rather than having only one transmission opportunity in each back-off cycle as traditional random back-off methods do, each station is allowed to have multiple transmission opportunities in each back-off cycle. Each transmission opportunity corresponds to a triggering point (an event from the triggering set) maintained by the station, and randomization of channel access is achieved by randomly selecting these triggering points from a constant/fixed back-off window. By controlling the number of triggering points adaptively responsive to the network congestion level, congestion avoidance is automatically achieved and the system performance oscillates around the optimal point.